package com.chapter10;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

import com.chapter10.Tnode;
import com.utility.Array;
import com.utility.RandomGenerator;
public class BinarySearchTree extends Tree{

	
	int size;
	BinarySearchTree(){
		super();
	}
	BinarySearchTree(Tnode r){
		super(r);
	}

	BinarySearchTree(int[] A){
		root=buildBST(A,0,A.length-1);
	}

	public void buildBST(int[] A){
		//we can take median to get better root 
		root=new Tnode(A[0]);
		for(int i=1;i<A.length;i++){
			insert(A[i]);
		}
	}

	public boolean isBST(){
		int numNodes=root.leftNodes+root.rightNodes+1;
		return isBST(root,Integer.MIN_VALUE,Integer.MAX_VALUE,numNodes);
	}
	public boolean isBST(Tnode node,int min, int max, int numNodes){
		if(node==null)
			return true;
		if(node.value<min || node.value>max)
			return false;
		if(numNodes!=node.leftNodes+node.rightNodes+1)
			return false;
		return isBST(node.left,min,node.value,node.leftNodes) && isBST(node.right,node.value,max,node.rightNodes);

	}
	public Tnode buildBST(int[] A, int l, int r){
		if(l>r)
			return null;
		//int mid=l+(r-l)/2;
		int mid=Array.median(A,l,r);
		Tnode node=new Tnode(A[mid]);
		size++;
		node.left=buildBST(A,l,mid-1);
		node.right=buildBST(A,mid+1,r);
		node.parent=null;
		if(node.left!=null){
			node.left.parent=node;
			node.leftNodes=node.left.leftNodes+node.left.rightNodes+1;
		}
		if(node.right!=null){
			node.right.parent=node;
			node.rightNodes=node.right.leftNodes+node.right.rightNodes+1;
		}
		return node;
	}

	
	public void preOrderTraversalIterative(){
		List<Tnode> s=new ArrayList<Tnode>();
		s.add(root);
		Tnode cur=root;
		while(!s.isEmpty())
		{
			cur=s.remove(s.size()-1);
			System.out.print(cur.value+" ");
			if(cur.right!=null)s.add(cur.right);
			if(cur.left!=null)s.add(cur.left);
		}
	}

	public Tnode[] search(Tnode current, Tnode parent,int value){
		Tnode[] nodePair=new Tnode[2];
		nodePair[0]=parent;
		nodePair[1]=current;
		if(current==null || current.value==value)
			return nodePair;
		if(current.value>value)
			return search(current.left,current,value);
		else 
			return search(current.right,current,value);
	}

	public void insert(int value){
		Tnode[] nodePair=search(root,null,value);
		if(nodePair[1]!=null)
			return;
		size++;
		Tnode newTNode= new Tnode(value);
		newTNode.parent=nodePair[0];
		if(nodePair[0].value>value)
			nodePair[0].left=newTNode;
		else
			nodePair[0].right=newTNode;

		Tnode current=newTNode;
		incrementNodeCount(current);

	}
	
	/*
	 * this is not correct inorder successor - check again
	 */
	public Tnode succesorBelow(Tnode node){
		Tnode current=node;
		if(current.right==null)
			return current;
		current=current.right;
		while(current.left!=null){
			current=current.left;
		}
		return current;
	}

	public Tnode PredecessorBelow(Tnode node){
		Tnode current=node;
		if(current.left==null)
			return current;
		current=current.left;
		while(current.right!=null){
			current=current.right;
		}
		return current;
	}

	public Tnode inOrderSuccesor(Tnode node){
		Tnode cur=node;
		if(cur.right!=null){
			cur=cur.right;
			while(cur.left!=null)
				cur=cur.left;
			return cur;
		}

		if(cur.parent.left==cur)
			return cur.parent;
		while(cur.parent!=null && cur.parent.right==cur)
		{
			cur=cur.parent;
		}

		return cur.parent;    
	}
	
	public Tnode inOrderPredecessor(Tnode node){
		Tnode cur=node;
		if(cur.left!=null){
			cur=cur.left;
			while(cur.right!=null)
				cur=cur.right;
			return cur;
		}
		if(cur.parent.right==cur)
			return cur.parent;
		while(cur.parent!=null && cur.parent.left==cur)
			cur=cur.parent;
		return cur.parent;
	}
	public Tnode findKthLargest(Tnode node, int K){
		if(K<0 || (K>node.leftNodes+1 && node.right==null))
			return null;
		if(node.leftNodes+1==K)
			return node;
		if(node.leftNodes>=K)
			return findKthLargest(node.left,K);
		else
			return findKthLargest(node.right,K-node.leftNodes-1);
	}

	public void delete(int value){
		Tnode[] pair = search(root, null,value);
		if(pair[1]==null)
			return;
		Tnode current=pair[1];
		Tnode parent=pair[0];
		if(current.left==null && current.right==null){
			decrementNodeCount(current);
			size--;
			if(parent.left==current)
				parent.left=null;
			else
				parent.right=null;
		}
		else if(current.left==null && current.right!=null){
			Tnode successor=succesorBelow(current);
			delete(successor.value);
			current.value=successor.value;
		}
		else{
			Tnode predecessor = PredecessorBelow(current);
			delete(predecessor.value);
			current.value=predecessor.value;
		}
	}

	
	public Tnode getBSTfromLevelOrder(int[] A){
		Tnode root=new Tnode(A[0]);
		int nP=0;// increments when left or right node is absent.
		List<NodeInfo> q=new ArrayList<NodeInfo>();
		NodeInfo nodeInfo = new NodeInfo(root,Integer.MAX_VALUE,Integer.MIN_VALUE,0);
		q.add(nodeInfo);
		NodeInfo current=nodeInfo;
		while(true){
			current=q.remove(0);
			int indexLeft=2*current.index +1-nP;
			if(indexLeft>=A.length)
				break;
			if(A[indexLeft]<A[current.index] && A[indexLeft] >current.min){
				current.node.left=new Tnode(A[indexLeft]);
				current.node.left.parent=current.node;
				current.node.leftNodes++;
				incrementNodeCount(current.node);
				q.add(new NodeInfo(current.node.left,A[current.index],current.min,indexLeft));
			}
			else
				nP++;
			int indexRight=2*current.index +2-nP;
			if(indexRight>=A.length)
				break;
			if(A[indexRight]>A[current.index] && A[indexRight] <current.max){
				current.node.right=new Tnode(A[indexRight]);
				current.node.right.parent=current.node;
				current.node.rightNodes++;
				incrementNodeCount(current.node);
				q.add(new NodeInfo(current.node.right,current.max,A[current.index],indexRight));
			}
			else
				nP++;

		}
		return root;
	}

	Tnode getClosestValue(Tnode root, int M){
	    return getClosestValue(root,null,M);
	}
	Tnode getClosestValue(Tnode node, Tnode prev,int M ){
		if(node==null)
			return prev;
	    if(node.value==M)
	        return node;
	    if(prev==null || Math.abs(M-prev.value)>Math.abs(M-node.value))
	    	prev=node;
	    
	    if(M>=node.value)
	        return getClosestValue(node.right,prev,M);
	    
	    return getClosestValue(node.left,prev,M);
	}
	
	public Tnode findMin(Tnode node){
		while(node.left!=null)
			node=node.left;
		return node;
	}
	
	public Tnode findMax(Tnode node){
		while(node.right!=null){
			node=node.right;
		}
		return node;
	}
	public NodePair twoSum(Tnode node, int M){
		Tnode minNode=findMin(node);
		Tnode maxNode=findMax(node);
		Tnode leftNode=minNode;
		Tnode rightNode=maxNode;
		while(leftNode!=maxNode){
			if(leftNode.value+rightNode.value==M)
				return new NodePair(leftNode, rightNode);
			while(leftNode.value+rightNode.value>M){
				rightNode=inOrderPredecessor(rightNode);
				if(rightNode==leftNode)
					break;
				if(leftNode.value+rightNode.value==M)
					return new NodePair(leftNode, rightNode);
			}
			leftNode=inOrderSuccesor(leftNode);
			rightNode=maxNode;
		}
		return new NodePair(null,null);
	}
	
	public List<Integer>findKClosestNodes(Tnode node, int M,int K){
		List<Tnode> l=findKClosestNodesUtil(node,M,K);
		List<Integer> l2=new ArrayList<Integer>();
		for(int i=0;i<l.size();i++)
			l2.add(l.get(i).value);
		System.out.println(l2 + " size ="+l2.size());
		return l2;
	}
	public List<Tnode> findKClosestNodesUtil(Tnode node, int M,int K){
		Tnode cur=getClosestValue(node,M);
		Tnode pred=cur;
		Tnode suc=inOrderSuccesor(cur);
		List<Tnode> predL=new ArrayList<Tnode>();
		List<Tnode> sucL=new ArrayList<Tnode>();
		int k=0;
		while((pred!=null || suc!=null) && k!=K){
			if(pred!=null && (suc==null || Math.abs(pred.value-M)<Math.abs(suc.value-M))){
				predL.add(pred);
				pred=inOrderPredecessor(pred);
				k++;
			}
			else {
				if(suc!=null){
					sucL.add(suc);
					suc=inOrderSuccesor(suc);
					k++;
				}
			}
		}
		
		predL.addAll(sucL);
		return predL;
	}
	
	public NodePair getllfromBST(Tnode node){
        NodePair p= getllfromBSTUtil(node);
        return p;
    }
	public NodePair getllfromBSTUtil(Tnode node){
        if(node==null || node.left==null && node.right==null)
            return new NodePair(node,node);
       
        NodePair left=getllfromBSTUtil(node.left);
        NodePair right=getllfromBSTUtil(node.right);
       
        if(node.left==null){
            node.right=right.first;
            right.first.left=node;
            return new NodePair(node,right.second);
        }
        if(node.right==null){
            node.left=left.second;
            left.second.right=node;
            return new NodePair(left.first,node);
        }
        node.right=right.first;
        right.first.left=node;
        node.left=left.second;
        left.second.right=node;
        return new NodePair(left.first,right.second);
	}
	public boolean testDelete(){

		for(int i=0;i<100;i++){
			insert(RandomGenerator.randInt(-50, 50));
			System.out.println(isBST());
		}

		System.out.println("Delete");
		System.out.println(size);
		for(int i=0;i<10;i++){
			int val=RandomGenerator.randInt(1, size);
			System.out.println("size = "+size+" value = "+val);
			Tnode t=findKthLargest(root, val);
			delete(t.value);
			levelOrderTraversal2(root);
			System.out.println(isBST());
		}
		return isBST();
	}

	
}


